package Sort;

import java.util.Random;

public class Main {

	public static int[] MergeSort(int myArray[]) {
		int A = myArray.length / 2;
		int B = myArray.length - A;
		int myArray1[] = new int[A];
		int myArray2[] = new int[B];

		for (int i = 0; i < A; i++) {
			myArray1[i] = myArray[i];
		}

		for (int i = A; i < A + B; i++) {
			myArray2[i - A] = myArray[i];
		}

		myArray1 = MergeSort(myArray1);
		myArray2 = MergeSort(myArray2);

		int i = 0, j = 0, k = 0;

		while (myArray1.length != j && myArray2.length != k) {
			if (myArray1[j] < myArray2[k]) {
				myArray[i] = myArray1[j];
				i++;
				j++;
			} else {
				myArray[i] = myArray2[k];
				i++;
				k++;
			}
		}

		while (myArray1.length != j) {
			myArray[i] = myArray1[j];
			i++;
			j++;
		}
		while (myArray2.length != k) {
			myArray[i] = myArray2[k];
			i++;
			k++;
		}

		return myArray;

	}

	public static void main(String[] args) {

		final int size = 10;
		int[] myArray = new int[size];
		Random random = new Random(15);
		System.out.println("myArray before:");
		for (int i = 0; i < size; i++) {
			myArray[i] = random.nextInt(30);
			System.out.printf("%5d", myArray[i]);
		}
		System.out.println();

		MergeSort(myArray);
		System.out.println("MyArray after MergeSort:");
		for (int i = 0; i < size; i++)
		System.out.printf("%5d", myArray[i]);
		System.out.println();
	}

}
